package cn.orange.ch08_backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * LC78.子集
 */
public class LC78 {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> trace = new ArrayList<>();
        backtracking(0, nums, trace, ans);
        return ans;
    }

    private void backtracking(int startIndex, int[] nums, List<Integer> trace, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(trace));
        if (startIndex >= nums.length) return;
        for (int i = startIndex; i < nums.length; i++) {
            int num = nums[i];
            trace.add(num);
            backtracking(i + 1, nums, trace, ans);
            trace.remove(trace.size() - 1);
        }
    }

    public static void main(String[] args) {
        LC78 alg = new LC78();
        System.out.println(alg.subsets(new int[]{1, 2, 3}));
        System.out.println(alg.subsets(new int[]{0}));
    }
}
